#ifndef __MNM_MESH_GRID_H
#define __MNM_MESH_GRID_H

#pragma once


#include "Tile.h"
#include "Profiler.h"

#include <SimpleHashLookUp.h>
#include <VectorMap.h>

namespace MNM
{
	struct OffMeshNavigation;

	struct MeshGrid
	{
		enum { x_bits = 11, }; // must add up to a 32 bit - the "tileName"
		enum { y_bits = 11, };
		enum { z_bits = 10, };
		
		enum { max_x = (1 << x_bits) - 1, };
		enum { max_y = (1 << y_bits) - 1, };
		enum { max_z = (1 << z_bits) - 1, };

		struct Params
		{
			Params()
				: origin(ZERO)
				, tileSize(16)
				, tileCount(1024)
				, voxelSize(0.1f)
			{
			}

			Vec3 origin;
			Vec3i tileSize;
			Vec3 voxelSize;
			uint32 tileCount;
		};

		struct WayQueryRequest
		{
			WayQueryRequest(TriangleID _from, TriangleID _to, const OffMeshNavigation& _offMeshNavigation, AStarOpenList& openList)
				: m_from(_from)
				, m_to(_to)
				, m_offMeshNavigation(_offMeshNavigation)
				, m_openList(openList)
			{

			}

			virtual ~WayQueryRequest(){}

			virtual bool CanUseOffMeshLink(const OffMeshLinkID linkID) const = 0;
			
			ILINE const TriangleID From() const { return m_from; }
			ILINE const TriangleID To() const { return m_to; }
			ILINE const OffMeshNavigation& GetOffMeshNavigation() const { return m_offMeshNavigation; }
			ILINE AStarOpenList& GetOpenList() { return m_openList; }
		
		private:
			const TriangleID m_from;
			const TriangleID m_to;
			const OffMeshNavigation& m_offMeshNavigation;
			AStarOpenList	&m_openList;
		};

		struct WayQueryResult
		{
			WayQueryResult(size_t waySize, bool finished)
				: m_waySize(waySize)
				, m_finished(finished)
			{

			}

			ILINE bool Finished() const { return m_finished; }
			ILINE bool Computing() const { return !m_finished; } 

			ILINE size_t GetWaySize() const { return m_waySize; }
		private:

			size_t m_waySize;
			bool   m_finished;	
		};

		MeshGrid();
		~MeshGrid();

		void Init(const Params& params);

		static inline size_t ComputeTileName(size_t x, size_t y, size_t z)
		{
			return (x & ((1 << x_bits) - 1)) |
				((y & ((1 << y_bits) - 1)) << x_bits) |
				((z & ((1 << z_bits) - 1)) << (x_bits + y_bits));
		}

		static inline void ComputeTileXYZ(size_t tileName, size_t& x, size_t& y, size_t& z)
		{
			x = tileName & (( 1 << x_bits) - 1);
			y = (tileName >> x_bits) & (( 1 << y_bits) - 1);
			z = (tileName >> (x_bits + y_bits)) & (( 1 << z_bits) - 1);
		}

		size_t GetTriangles(aabb_t aabb, TriangleID* triangles, size_t maxTriCount) const;
		TriangleID GetTriangleAt(const vector3_t& location, const real_t verticalDownwardRange, const real_t verticalUpwardRange) const;
		bool IsTriangleAcceptableForLocation(const vector3_t& location, TriangleID triangleID) const;
		TriangleID GetClosestTriangle(const vector3_t& location, real_t vrange, real_t hrange,
			real_t* distSq = 0, vector3_t* closest = 0) const;

		bool GetVertices(TriangleID triangleID, vector3_t& v0, vector3_t& v1, vector3_t& v2) const;
		bool GetTriangle(TriangleID triangleID, Tile::Triangle& triangle) const;

		bool PushPointInsideTriangle(const TriangleID triangleID, vector3_t& location, real_t amount) const;
	
		inline size_t GetTriangleCount() const 
		{ 
			return m_triangleCount; 
		}

		void AddOffMeshLinkToTile(const TileID tileID, const TriangleID triangleID, const uint16 offMeshIndex);
		void UpdateOffMeshLinkForTile(const TileID tileID, const TriangleID triangleID, const uint16 offMeshIndex);
		void RemoveOffMeshLinkFromTile(const TileID tileID, const TriangleID triangleID);

		WayQueryResult FindWay(WayQueryRequest& inputRequest, WayTriangleData* outputWay, size_t maxWayTriCount) const;

		void PullString(const vector3_t from, const TriangleID fromTriID, const vector3_t to, const TriangleID toTriID, vector3_t& middlePoint) const;

		struct RayHit
		{
			TriangleID triangleID;
			real_t distance;
			size_t edge;
		};

		/*
			********************************************************************************************
			RayCastRequestBase holds the actual request information needed to perform a RayCast request.
			It needs to be constructed through the RayCastRequest that assures the presence of the way.
			********************************************************************************************
		*/

		struct RaycastRequestBase
		{
		protected:
			// This class can't be instantiated directly.
			RaycastRequestBase(const size_t _maxWayTriCount)
			:maxWayTriCount(_maxWayTriCount)
			{}

		public:
			RayHit			hit;
			TriangleID*		way;
			size_t			wayTriCount;
			const size_t	maxWayTriCount;
		};

		template<size_t MaximumNumberOfTrianglesInWay>
		struct RayCastRequest: public RaycastRequestBase
		{
			RayCastRequest()
			:RaycastRequestBase(MaximumNumberOfTrianglesInWay)
			{
				way = &(wayArray[0]);
				wayTriCount = 0;
			}
		private:
			TriangleID wayArray[MaximumNumberOfTrianglesInWay];
		}; 

		// ********************************************************************************************

		enum ERayCastResult
		{
			eRayCastResult_NoHit = 0,
			eRayCastResult_Hit,
			eRayCastResult_RayTooLong,
			eRayCastResult_Unacceptable,
		};

		ERayCastResult RayCast(const vector3_t& from, TriangleID fromTri, const vector3_t& to, TriangleID toTri,
			RaycastRequestBase& wayRequest) const;

		TileID SetTile(size_t x, size_t y, size_t z, Tile& tile);
		void ClearTile(TileID tileID, bool clearNetwork = true);
		
		void CreateNetwork();
		void ConnectToNetwork(TileID tileID);

		inline bool Empty() const
		{
			return m_tileCount == 0;
		}

		inline size_t GetTileCount() const
		{
			return m_tileCount;
		}

		TileID GetTileID(size_t x, size_t y, size_t z) const;
		const Tile& GetTile(TileID) const;
		Tile& GetTile(TileID);

		void Swap(MeshGrid& other);

		inline const Params& GetParams() const
		{
			return m_params;
		}

		void Draw(size_t drawFlags, TileID excludeID = 0) const;

		bool CalculateMidEdge(const TriangleID triangleID1, const TriangleID triangleID2, Vec3& result) const;

		enum ProfilerTimers
		{
			NetworkConstruction = 0,
		};

		enum ProfilerMemoryUsers
		{
			TriangleMemory = 0,
			VertexMemory,
			BVTreeMemory,
			LinkMemory,
			GridMemory,
		};

		enum ProfilerStats
		{
			TileCount = 0,
			TriangleCount,
			VertexCount,
			BVTreeNodeCount,
			LinkCount,
		};

		typedef Profiler<ProfilerMemoryUsers, ProfilerTimers, ProfilerStats> ProfilerType;
		const ProfilerType& GetProfiler() const;

#if MNM_USE_EXPORT_INFORMATION
		enum EAccessibilityRequestValue
		{
			eARNotAccessible = 0,
			eARAccessible = 1
		};

		struct AccessibilityRequest
		{
			AccessibilityRequest(TriangleID _from, const OffMeshNavigation& _offMeshNavigation)
				: m_from(_from)
				, m_offMeshNavigation(_offMeshNavigation)
			{

			}

			ILINE const TriangleID From() const { return m_from; }
			ILINE const OffMeshNavigation& GetOffMeshNavigation() const { return m_offMeshNavigation; }

		private:
			const TriangleID m_from;
			const OffMeshNavigation& m_offMeshNavigation;
		};

		void ResetAccessibility(uint8 accessible);
		void ComputeAccessibility(const AccessibilityRequest& inputRequest);
#endif

	protected:
		void Grow(size_t amount);
		TileID GetNeighbourTileID(size_t x, size_t y, size_t z, size_t side) const;
		void ComputeAdjacency(size_t x, size_t y, size_t z, const real_t& toleranceSq, Tile& tile);
		void ReComputeAdjacency(size_t x, size_t y, size_t z, const real_t& toleranceSq, Tile& tile,
			size_t side, size_t tx, size_t ty, size_t tz, TileID targetID);

		struct TileContainer
		{
			TileContainer()
				: x(0)
				, y(0)
				, z(0)
			{
			}

			uint32 x : x_bits;
			uint32 y : y_bits;
			uint32 z : z_bits;

			Tile tile;
		};

		TileContainer* m_tiles;
		size_t m_tileCount;
		size_t m_tileCapacity;
		size_t m_triangleCount;

		typedef std::vector<size_t> Frees;
		Frees m_frees;

		// replace with something more efficient will speed up path-finding, ray-casting and
		// connectivity computation		
		typedef std::map<uint32, uint32> TileMap;
		TileMap m_tileMap;

		typedef std::vector<WayTriangleData> TNextLinkedTriangles; 
		mutable  TNextLinkedTriangles	m_nextLinkedTriangles;

		Params m_params;
		ProfilerType m_profiler;

		static const real_t kMinPullingThreshold;
		static const real_t kMaxPullingThreshold;
	};
}

#endif	// #ifndef __MNM_MESH_GRID_H
